/* by wade.hit@gmail.com  */
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "defines.h"
#include "buddy_system.h"

/*
   typedef struct WORD
   {
   int llink;	
   int tag;	
   int kval; 
   int rlink;
   }WORD, * space;
 */

//#progma pack (1)
typedef struct WORD
{
	char bit[8]; //3 3 .5+.5 1
}WORD, * space; 
//#progma pack ()

typedef struct head_node
{
	int nodesize;
	int first;
	//}free_list[FREE_LIST_LENGTH + 1]; 
}*free_list;

static	FILE*		log_file=NULL;
static	int		bitmap_fd;

static	space		start_addr;
static	free_list	flist;
static	int		FREE_LIST_LENGTH = 26;
static	int		CHUNK_MAX_CNT;

static int buddy_alloc( int n);
static int buddy(int );
static int cut(int);
static void buddy_reclaim(int id); 

static void _set_left_link(int cur_id, int val_id);
static void _set_right_link(int cur_id, int val_id);
static void _set_tag_0(int cur_id);
static void _set_tag_1(int cur_id);
static void _set_kval(int cur_id, int kval);
static int _get_left_link(int cur_id);
static int _get_right_link(int cur_id);
static int _get_tag(int cur_id);
static int _get_kval(int cur_id);

static char* image=NULL;



STATE disk_init(INIT_TYPE init_type, char* g_image, char* bitmap_filename, char* buddy_log, int space_max_cnt)
{
	int i;

	//bitmap_fd=open(bitmap_filename, O_RDWR | O_CREAT | O_NONBLOCK, S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP);
	if (buddy_log)
	{
		log_file=fopen(buddy_log, "w");
		if (log_file==NULL)
		{
			printf ("errno:  create %s falied.\n", buddy_log);
			return DISK_INIT_FAIL;
		}
	}

	image=g_image;

	start_addr=(WORD*) (g_image+IMAGE_K_BUDDY*1024);
	flist=(free_list) (g_image+IMAGE_K_BASIS*1024+IMAGE_BUDDY_FLIST);

	FREE_LIST_LENGTH=*((int*)(g_image+IMAGE_K_BASIS*1024+IMAGE_BUDDY_FLEN));
	CHUNK_MAX_CNT=*((int*)(g_image+IMAGE_K_BASIS*1024+IMAGE_BUDDY_MAX_CNT));

	if (init_type==INIT_TYPE_LOAD) printf ("%d %d\n", FREE_LIST_LENGTH, CHUNK_MAX_CNT);
	if (init_type==INIT_TYPE_CREATE)
	{
		printf ("init_type_create.\n");
		memset(start_addr, 0, IMAGE_K_BUDDY_SIZE*1024);
		FREE_LIST_LENGTH = 26;
		for (i = 0; i <= FREE_LIST_LENGTH; i++)
		{
			flist[i].nodesize = (int)pow(2, i);
			flist[i].first = FREE_LIST_NOT_AVAIL;
		}

		int number = cut(space_max_cnt);
		int remain_space = 0;
		if (number >= 0) 
		{
			FREE_LIST_LENGTH = number;
			CHUNK_MAX_CNT = space_max_cnt;
		}
		else 
		{
			FREE_LIST_LENGTH = 0;
			CHUNK_MAX_CNT = 0;
			return DISK_INIT_FAIL;
		}
		while(number >= 0)
		{
			//add small space to flist
			_set_tag_0(remain_space);
			_set_kval(remain_space, number);
			if ( flist[number].first == FREE_LIST_NOT_AVAIL)
			{
				_set_right_link(remain_space, remain_space);
				_set_left_link(remain_space, remain_space);
				flist[number].first = remain_space;
			}
			remain_space = remain_space + (int)pow(2, number);
			number = cut(space_max_cnt - remain_space);
		}
	}

	return DISK_INIT_SUCCESS;
}

void disk_exit()
{
	*( (int*)(image+IMAGE_K_BASIS*1024+IMAGE_BUDDY_FLEN) )=FREE_LIST_LENGTH;
	*( (int*)(image+IMAGE_K_BASIS*1024+IMAGE_BUDDY_MAX_CNT) )=CHUNK_MAX_CNT;
	
	if (log_file)
	{
		fprintf (log_file, "exit....\n");	
		fclose(log_file);
	}
	close(bitmap_fd);
}

PTR_DISK disk_alloc(int chunk_cnt)
{
	int i;

	int addr_id = buddy_alloc(chunk_cnt);
	if (addr_id==FREE_LIST_NOT_AVAIL)
	{
		if (log_file)
		{
			fprintf(log_file, "Buddy_alloc failed. chunk_cnt=%d\n",chunk_cnt);
			fflush(log_file);
		}
		return DISK_ALLOC_FAIL;
	}
	else
	{
		PTR_DISK locate = addr_id;
		if (log_file)
		{
			fprintf(log_file, "%d @ %d\n", chunk_cnt, locate);
			fflush(log_file);
		}
		return locate;
	}
}

void disk_free(PTR_DISK disk_loc_id)
{
	if (log_file)
	{
		fprintf (log_file, "free:%d\n", disk_loc_id);
		fflush(log_file);
	}
	buddy_reclaim(disk_loc_id);
}


static int buddy_alloc(int n)
{
	int i, k;
	int cur_id, pre_id, suc_id, pi_id;

	for (k = 0; k <= FREE_LIST_LENGTH && (flist[k].nodesize < n || flist[k].first == FREE_LIST_NOT_AVAIL); k++);

	if (k > FREE_LIST_LENGTH || n <= 0)
	{
		if (n <= 0) 
		{
			if (log_file)
			{
				fprintf(log_file, "alloc %d space is not correct\n", n);
			}
		}
		return FREE_LIST_NOT_AVAIL; 
	}
	else
	{
		cur_id=flist[k].first;

		pre_id=_get_left_link(cur_id);
		suc_id=_get_right_link(cur_id);

		if (cur_id == suc_id)
		{
			flist[k].first = FREE_LIST_NOT_AVAIL;
		}
		else
		{
			_set_right_link(pre_id, suc_id);
			_set_left_link(suc_id, pre_id);
			flist[k].first=suc_id;
		}	

		for (i = 1; (k-i<=FREE_LIST_LENGTH)&& (k-i>=0)&& (flist[k-i].nodesize >=n); i++)
		{
			pi_id=cur_id + (int)pow(2,k-i);
			_set_right_link(pi_id, pi_id);
			_set_left_link(pi_id, pi_id);	
			_set_tag_0(pi_id);
			_set_kval(pi_id, k-i);
			flist[k-i].first=pi_id;
		}
		_set_tag_1(cur_id);
		_set_kval(cur_id, (k-(--i)) );
	}
	return cur_id;
}

/* just return an id */
static int buddy (int p_id)
{
	int p_kval=_get_kval(p_id);

	if ( p_id % ((int)pow(2, p_kval+1)) == 0 )	
	{
		return p_id+(1<<p_kval);
	}

	return p_id-(1<<p_kval);
}

static void buddy_reclaim(int free_id) 
{
	int free_buddy_id, p_kval, s_kval;

	if    ( (free_id<0)  ||  (free_id>=CHUNK_MAX_CNT)  )
	{
		if (log_file)
		{
			fprintf(log_file, "addr is not illegal, reclaim failed\n");
		}
		return ;
	}


	free_buddy_id= buddy(free_id);

	while ( free_buddy_id >= 0 && 
			free_buddy_id < CHUNK_MAX_CNT &&
			_get_tag(free_buddy_id)==0 &&
			_get_kval(free_id)==_get_kval(free_buddy_id)   )
	{
		if ( _get_left_link(free_buddy_id)==free_buddy_id  && _get_right_link(free_buddy_id)==free_buddy_id )	
		{
			flist[ _get_kval(free_buddy_id) ].first=FREE_LIST_NOT_AVAIL;		
		}
		else
		{
			_set_right_link( _get_left_link(free_buddy_id), _get_right_link(free_buddy_id) );	
			_set_left_link( _get_right_link(free_buddy_id), _get_left_link(free_buddy_id) );
			s_kval=_get_kval(free_buddy_id);
			if ( flist[ s_kval ].first == free_buddy_id )
			{
				flist[s_kval].first=_get_right_link(free_buddy_id);
			}
		}

		p_kval=_get_kval(free_id);
		if ( free_id % (int)pow(2,p_kval+1) == 0)
		{
			_set_kval(free_id, p_kval+1);	
		}
		else
		{
			_set_kval(free_buddy_id, p_kval+1);
			free_id=free_buddy_id;		
		}
		free_buddy_id=buddy(free_id);	
	}



	_set_tag_0(free_id);
	p_kval=_get_kval(free_id);
	if ( flist[p_kval].first == FREE_LIST_NOT_AVAIL)
	{
		_set_right_link(free_id, free_id);
		_set_left_link(free_id, free_id);
		flist[p_kval].first=free_id;
	}
	else
	{
		_set_right_link(free_id, flist[p_kval].first);
		_set_left_link(free_id,  _get_left_link(flist[p_kval].first)  );  		
		_set_left_link( _get_right_link(free_id),  free_id);
		_set_right_link( _get_left_link(free_id),  free_id);
		flist[p_kval].first=free_id;		
	}
}


static void _set_left_link(int id, int value)
{
	/*
	   p value: AAAABBBB -> AAAA0000 
	   q bit:   CCCCDDDD -> 0000DDDD 
	 */
	char p,q;
	int i;

	p= (value&0x000000ff);
	start_addr[id].bit[0]=p;
	p=(value&0x0000ff00 ) >> 8;
	start_addr[id].bit[1]=p;
	p=(value&0x00ff0000 ) >> 16;
	start_addr[id].bit[2]=p;


	p=(value&0xff000000)>>24;
	p=p&0x0f;

	q=start_addr[id].bit[6];
	q=q&0xf0;

	start_addr[id].bit[6]=p | q;
}

static void _set_right_link(int id, int value)
{
	/*
	   p value: AAAABBBB -> AAAA0000 -> 0000AAAA
	   q bit:   CCCCDDDD -> CCCC0000 
	 */
	char p,q;
	int i;
	p= (value&0x000000ff);
	start_addr[id].bit[3]=p;
	p=(value&0x0000ff00)>>8;
	start_addr[id].bit[4]=p;
	p=(value&0x00ff0000)>>16;
	start_addr[id].bit[5]=p;

	p=(value&0xff000000)>>24;
	p=p&0x0f;
	p=p<<4;

	q=start_addr[id].bit[6];
	q=q&0x0f;

	start_addr[id].bit[6]=p | q;
}

static void _set_tag_0(int id)
{
	/*
	   bit[7] p : ABCD EFGH -> ABCD EFG0
	   1111 1110
	 */
	int i;
	start_addr[id].bit[7]&=0x7f;
}

static void _set_tag_1(int id)
{
	/*
	   bit[7] p : ABCD EFGH -> ABCD EFG0
	   0000 0001
	 */
	int i;
	start_addr[id].bit[7]|=0x80;
}

static void _set_kval(int id, int value)
{
	/*
	   p value : CCCC CC00
	   bit[7] q : AAAA AAAB -> 0000 000B
	 */
	int i;
	char p,q;
	p=value & 0x000000ff;
	q=start_addr[id].bit[7]&0x80;
	start_addr[id].bit[7]=p|q;
}

static int _get_left_link(int id)
{
	/*
	   [0] [1] [2] [6.0]
	   bit[6] : AAAABBBB -> AAAA0000 
	 */
	int result=0;
	char p;

	result=(start_addr[id].bit[6]&0x0f);
	result<<=8;
	result|=(start_addr[id].bit[2])&0xff;
	result<<=8;
	result|=(start_addr[id].bit[1])&0xff;
	result<<=8;
	p=(start_addr[id].bit[0])&0xff;
	result|=(p&0xff);
	/* BUg
	   result+=p;
	 */

	//	bit_show(result);
	if (result>=CHUNK_MAX_CNT || result<0) return FREE_LIST_NOT_AVAIL;
	return result;
}

static int _get_right_link(int id)
{
	/*
	   [3]  [4] [5] [6.5]
	   bit[6] : AAAABBBB -> 0000BBBB
	 */
	int result=0;
	char p;
	result=(start_addr[id].bit[6])&0xf0;
	result>>=4;
	result<<=8;
	result|=(start_addr[id].bit[5])&0xff;
	result<<=8;
	result|=(start_addr[id].bit[4])&0xff;
	result<<=8;
	result|=(start_addr[id].bit[3])&0xff;

	//	bit_show(result);

	if (result>=CHUNK_MAX_CNT || result<0) return FREE_LIST_NOT_AVAIL;
	return result;
}

static int _get_tag(int id)
{
	/*
	   [7] AAAAAAAB -> AAAAAAA0
	   00000001
	 */
	if ((start_addr[id].bit[7]&(1<<7))==0) return 0;
	return 1;
}

static int _get_kval(int id)
{
	/*
	   [7] AAAAAAAB -> AAAAAAA0
	   -> 11111110
	 */
	char p=0;
	p=start_addr[id].bit[7]&0x7f;	
	return (int)p;
}


void show_bit_char(char p)
{
	int i;
	for (i=0; i<8; i++)
		if ( (p&(1<<i)) ==0) printf ("0"); else printf ("1");
	printf (" ");
}

void bit_show(int num)
{
	int i;
	for (i=0;i<32;i++)
	{
		if ( (num&(1<<i))==0 )
		{
			printf ("0");
		}	
		else
		{
			printf ("1");
		}

		if ( i%8==7 )
		{
			printf (" ");
		}
	}
	printf ("\n");
}

static int cut(int cnt)
{
	int i;
	if (cnt <= 0) return -1;
	for (i = 26; i >= 0; i--)
	{
		if ((int)pow(2, i) <= cnt)
		{
			return i;
		}
	}
}

void disk_show()
{
	int i;
	printf ("FreeList length: %d\nMax chunk cnt:%d\n", FREE_LIST_LENGTH, CHUNK_MAX_CNT);
	for (i = 0; i <= FREE_LIST_LENGTH; i++)
	{
		printf("i = %d:\t", i);
		if (flist[i].first == FREE_LIST_NOT_AVAIL) printf("FREE_LIST_NOT_AVAIL");
		else
		{
			int id = flist[i].first;
			do
			{
				printf("id = %d, kval = %d\n", id, _get_kval(id));
				id = _get_right_link(id);
			} while (id != flist[i].first);
		}
		printf("\n");
	}
	printf ("\n\n");
}

	
void disk_bitmap(FILE* fd)
{
	int i,id;
	for (i=0; i<=FREE_LIST_LENGTH; i++)
	{
		if (flist[i].first==FREE_LIST_NOT_AVAIL) continue;
		id=flist[i].first;
		do
		{
			fprintf (fd, "%d %d\n", 1<<i, id);
			id=_get_right_link(id);
		}while (id!=flist[i].first);
	}
}
